//package com.gitee.feizns.explore.data_structure.linked_list.singly.insertionSortList;
//
///**
// * @author feizns
// * @since 2019/11/12
// */
//public class Main2 {
//
//    public ListNode insertionSortList(ListNode head) {
//        if (head == null || head.next == null) {
//            return head;
//        }
//        ListNode left = head;
//        ListNode right = head.next;
//        while (right != null && right.next != null) {
//            left = left.next;
//            right = right.next.next;
//        }
//        right = left.next;
//        left.next = null;
//        ListNode result = new ListNode(0);
//        ListNode resultHead = result;
//        ListNode leftNode = insertionSortList(head);
//        ListNode rightNode = insertionSortList(right);
//        while (leftNode != null && rightNode != null) {
//            if (leftNode.val < rightNode.val) {
//                result.next = leftNode;
//                result = result.next;
//                leftNode = leftNode.next;
//            } else {
//                result.next = rightNode;
//                result = result.next;
//                rightNode = rightNode.next;
//            }
//        }
//        result.next = leftNode == null ? rightNode : leftNode;
//        return resultHead.next;
//    }
//
//}
